/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package knn;

import java.text.DecimalFormat;
import java.util.TreeSet;
import Javabeans.Attribute;
import java.util.Iterator;
import Javabeans.DatPoint;
import Javabeans.DataSet;
import csvloader.CSVLoader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;
import static java.lang.System.out;

/**
 *
 * @author Muhammed
 */
public class KNN_1 {
    private double learningRate = 1;
    private DataSet trainData;
    private DataSet testData;
    private int positiveClassifications;
    private int misClassifications;
    private DecimalFormat df = new DecimalFormat("###,###,##0.0000");
    DatPoint[][] tempFolds = null;

    public void loadTraining(String path, String filename) throws IOException {
        this.setTrainData(loadDataSet(path, filename));
    }

    public void loadTesting(String path, String filename) throws IOException {
        this.setTestData(loadDataSet(path, filename));
    }

    private DataSet loadDataSet(String path, String filename) throws IOException {
        CSVLoader csvloader = new CSVLoader(path, filename);
        DataSet dataSet = csvloader.getDataSet();
        return dataSet;
    }

    public double crossValidate(int folds, int numOfNeighbors, boolean printFlag, boolean includeWeights) throws CloneNotSupportedException {
        this.positiveClassifications = 0;
        this.misClassifications = 0;

        this.setTestData(new DataSet());
        
        if(tempFolds==null)
            tempFolds = getFolds(folds);

        ArrayList<DatPoint> originalTrainData = new ArrayList<DatPoint>();
        ArrayList<DatPoint> tempDPList1 = this.trainData.getDataPoints();
        Iterator it = tempDPList1.iterator();
        while(it.hasNext()){
            DatPoint temp = (DatPoint) it.next();
            originalTrainData.add((DatPoint) temp.clone());
        }
        if(includeWeights)
            this.calculateWeights(this.trainData.getAttributes().size()-1);
        //out.println("Number of Folds: " + tempFolds.length);
        //out.println("Number of Neighbours: " + numOfNeighbors);
        int count = 0;
        //out.println("----------------CrossValidating----------------");
        double precision=0.0;
        double oldPrecision=0;
        double newPrecision=0.0;
        
        for (DatPoint[] fold : tempFolds) {
            ArrayList<DatPoint> tempClone = new ArrayList<DatPoint>();
            ArrayList<DatPoint> tempDPList11 = originalTrainData;
            it = tempDPList11.iterator();
            while(it.hasNext()){
                DatPoint temp = (DatPoint) it.next();
                tempClone.add((DatPoint) temp.clone());
            }

            this.trainData.setDataPoints(tempClone);

            
            //Print the elements in this fold
            //out.println("Fold#" + count++ + " with " + fold.length + " records.");
            count++;
            if (printFlag) {
                int c = 0;
                for (DatPoint d : fold) {
                    out.println("\t" + c++ + ") " + d);
                }
            }
            
            //Make fold the test and remove datapoints in fold from training
            for (DatPoint d : fold) {
                this.testData.add(d);

                ArrayList<DatPoint> tempDPList = this.trainData.getDataPoints();
                it = tempDPList.iterator();
                while(it.hasNext()){
                    DatPoint tempDP = (DatPoint) it.next();
                    if((tempDP.compareTo(d)==0)){
                        it.remove();
                    }
                }
            }
            
            //Normalize all the attributes based on training data
            //out.println("1 - Normalized all the attribtues");
            this.normalizeTrainingDataSet();

            //Clone fold data points so we can compare it to predicted
            ArrayList<DatPoint> originalTestingList = new ArrayList<DatPoint>();
            it = this.getTestData().getDataPoints().iterator();
            while (it.hasNext()) {
                DatPoint dp = (DatPoint) it.next();
                if (dp != null) {
                    originalTestingList.add((DatPoint) dp.clone());
                } else {
                    originalTestingList.add(null);
                }
            }

            //Predict outputs for all the datapoints in the testing set
            precision=this.predictTestingSet(numOfNeighbors, printFlag, includeWeights);
            
            oldPrecision=newPrecision;
            newPrecision=0;
            this.getTestData().setDataPoints(new ArrayList<DatPoint>());
            
        }
        double avgPrecision = precision;
        double[] w = this.trainData.getWeights();
        double tempTotal=0;
        boolean isFirst=true;
        
        for(double d:w){
            if(isFirst){
                out.print(df.format(d));
                isFirst=false;
            }else{
                out.print(","+df.format(d));
            }
            tempTotal+=d;
        }
         
        out.print(","+df.format(tempTotal));
        out.println(","+avgPrecision);

        this.trainData.setDataPoints(originalTrainData);

        return avgPrecision;
    }

    private DatPoint[][] getFolds(int numberOfFolds) throws CloneNotSupportedException {
        //Get how many datapoints per fold
        int trainingSize = this.getTrainData().getDataPoints().size();
        int foldSize = trainingSize / numberOfFolds;
        
        if(trainingSize==numberOfFolds){
            foldSize=1;
        }else{
            int mod = trainingSize % numberOfFolds;
            if (mod != 0) {
                foldSize++;
            }
        }

        //Randomly pick datapoints to be placed in each fold
        DatPoint[][] folds = new DatPoint[numberOfFolds][foldSize];
        DataSet tempTrainingSet = (DataSet) this.getTrainData().clone();

        Random randomGenerator;
        int random;
        for (int i = 0; i < foldSize; i++) {
            for (int j = 0; j < numberOfFolds && tempTrainingSet.size() > 0; j++) {
                randomGenerator = new Random();
                random = randomGenerator.nextInt(tempTrainingSet.size());
                folds[j][i] = tempTrainingSet.getDataPoint(random);
                tempTrainingSet.remove(random);
            }
        }
        
        return folds;
    }

    public double predictTestingSet(int numOfNeighbors, boolean printFlag, boolean includeWeights) {
        int outputIndex = this.getTrainData().getOutputIndex() - 1;

        for (int i = 0; i < this.getTestData().size(); i++) {
            DatPoint testPoint = this.getTestData().getDataPoint(i);
            if (testPoint != null) {

                //Get the specified number of neighbour points to the test point.
                
                HashMap<DatPoint, Double> neighboursMap = getNeighbours(numOfNeighbors, testPoint, printFlag);
                //out.println("-----------------------------------------");
                //Predict output based on neighbours
                HashMap<String, Double> tempOutputMap = new HashMap<String, Double>();
                if (neighboursMap != null) {
                    Iterator<DatPoint> it = neighboursMap.keySet().iterator();
                    boolean isFirst = true;
                    while (it.hasNext()) {
                        DatPoint temp = it.next();
                        double distance = neighboursMap.get(temp);
                        String key = temp.getData(outputIndex);
                        Double value = tempOutputMap.get(key);
                        if (value == null) {
                            value = distance;
                            tempOutputMap.put(key, value);
                        } else {
                            value += distance;
                            tempOutputMap.remove(key);
                            tempOutputMap.put(key, value);
                        }
                    }
                    String actual = testPoint.getData(outputIndex);
                    String predicted = getPrediction(tempOutputMap);
                    if (actual!=null&&predicted!=null&&(actual.compareTo(predicted)) == 0) {
                        ++this.positiveClassifications;
                    } else {
                        ++this.misClassifications;
                        if(includeWeights)
                            this.adjustWeights(1, learningRate);
                    }
                    
                    //testPoint.setData(outputIndex, predicted);
                    if (printFlag) {
                        out.print(i + "," + testPoint+",");
                        /*
                        it = neighboursMap.keySet().iterator();
                        isFirst = true;
                        while (it.hasNext()) {
                            DatPoint temp = it.next();
                            double distance = neighboursMap.get(temp);
                            if (isFirst) {
                                out.print(temp.getData(outputIndex) + "("
                                        + df.format(distance) + ")");
                                isFirst = false;
                            } else {
                                out.print(", " + temp.getData(outputIndex) + "("
                                        + df.format(distance) + ")");
                            }
                        }
                         * 
                         */
                        out.println(predicted+"");
                    }else{
                        //out.println(i + ") actual: " + actual + " predicted: " + predicted);
                    }
                } else {
                    out.println("Unable to get make a prediction from training dataset.");
                }
            }

        }
        
        //out.println("\t----------------Precision--------------");
        //out.println("\tMisclassifications: " + this.misClassifications);
        //out.println("\tPositive Cclassifications: " + this.positiveClassifications);
         
        double total = this.positiveClassifications + this.misClassifications;
        //out.println("\tPrecision: " + df.format((this.positiveClassifications / total) * 100));
        //out.println("-----------------------------------------------");
        return (this.positiveClassifications / total) * 100;
    }

    public void normalizeTrainingDataSet() {
        ArrayList<Attribute> att = this.getTrainData().getAttributes();
        ArrayList<DatPoint> data = this.getTrainData().getDataPoints();

        double max,min;
        
        int count = att.size();
        for (int i = 0; i < count; i++) {
            max = Double.MIN_NORMAL;
            min = Double.MAX_VALUE;
            if (i != this.getTrainData().getOutputIndex() - 1) {
                Attribute attribute = att.get(i);
                
                if ((attribute.getType().compareTo(Attribute.NUMERIC)) == 0) {
                    Iterator it = data.iterator();
                    double tempValue;
                    while (it.hasNext()) {
                        DatPoint tempPoint = (DatPoint) it.next();
                        tempValue = Double.parseDouble(tempPoint.getData(i));
                        if (tempValue > max) {
                            max = tempValue;
                        }
                        if (tempValue < min) {
                            min = tempValue;
                        }
                    }
                    attribute.setMax(max);
                    attribute.setMin(min);
                    //out.println("\t" + attribute.getName() + " - " + "min: "+ attribute.getMin() + " max: " + attribute.getMax());
                }
            }
        }
        //out.println("-----------------------------------------------");
    }

    private HashMap<DatPoint, Double> getNeighbours(int numOfNeighbors, DatPoint testPoint, boolean printFlag) {
        Iterator<DatPoint> it = (this.getTrainData().getDataPoints()).iterator();

        HashMap<DatPoint, Double> similarityMap = new HashMap<DatPoint, Double>();
        
        while (it.hasNext()) {
            DatPoint trainPoint = it.next();
            Double dist = distance(trainPoint, testPoint);
            Double similarity = 1/dist;
            //out.println(similarity);
            
            similarityMap.put(trainPoint, similarity);
        }

        if (!similarityMap.isEmpty()) {
            similarityMap = sortSimilarityMap(similarityMap, numOfNeighbors);
            return similarityMap;
        }

        return null;
    }

    public Double distance(DatPoint point1, DatPoint point2) {
        String[] pointA = point1.getData();
        String[] pointB = point2.getData();
        String a, b;

        int count = 0;
        if (pointA.length == pointB.length) {
            count = pointA.length;
        } else {
            return null;
        }

        ArrayList<Attribute> attributes = this.getTrainData().getAttributes();
        double distance = 0.0;

        for (int i = 0; i < count; i++) {
            if (i != getTrainData().getOutputIndex() - 1) {
                a = pointA[i];
                b = pointB[i];
                Attribute att = attributes.get(i);
                if(att!=null && att.getType()!=null){
                    if (att.getType().compareTo(Attribute.NOMINAL) == 0) {
                        double temp = (1 - getSim(a, b, i));
                        distance += temp;
                    } else {
                        double temp = Math.pow(
                                (att.getWeight()*(normalizeAttribute(i, Double.parseDouble(a))))
                                - att.getWeight()*(normalizeAttribute(i, Double.parseDouble(b))), 2);
                        distance += temp;
                    }
                }
            }
        }
        distance = Math.sqrt(distance);
        return distance;
    }

    public Double getSim(String a, String b, int attIndex) {
        Attribute att = this.getTrainData().getAttributes().get(attIndex);
        HashMap<String, Double> matrix = att.getSimilarityMatrix();
        String key = a + "-" + b;
        Double d = matrix.get(key);
        if (d == null) {
            key = b + "-" + a;
            d = matrix.get(key);
        }
        //System.out.println(key+" - "+d);
        return d;
    }

    private double normalizeAttribute(int attIndex, double value) {
        Attribute attribute = this.getTrainData().getAttributes().get(attIndex);
        double max = attribute.getMax();
        double min = attribute.getMin();
        double temp = (value - min) / (max - min);
        return temp;
    }

    public void setOutputAttribute(int i) {
        if (getTrainData() != null) {
            getTrainData().setOutputIndex(i);
        }
        if (getTestData() != null) {
            getTestData().setOutputIndex(i);
        }
    }

    private HashMap<DatPoint, Double> sortSimilarityMap(HashMap<DatPoint, Double> similarityMap, int numOfNeighbours) {
        HashMap<DatPoint, Double> tempMap = new HashMap<DatPoint, Double>();

        ArrayList<DatPoint> tempKeys = new ArrayList<DatPoint>(similarityMap.keySet());
        ArrayList<Double> tempValues = new ArrayList<Double>(similarityMap.values());
        TreeSet<Double> sortedSet = new TreeSet<Double>(tempValues);
        
        Object[] sortedArray = sortedSet.toArray();
        int size = numOfNeighbours;
        int total = sortedArray.length-1;
        if(total==0){
            out.println("No similarities found in Map");
            return null;
        }
        for (int i = total; i > total-size; i--) {
            if(i<sortedArray.length)
                tempMap.put(
                        (DatPoint) tempKeys.get(tempValues.indexOf((Double) sortedArray[i])),
                        (Double) sortedArray[i]);
        }
        return tempMap;
    }

    private String getPrediction(HashMap<String, Double> tempOutputMap) {
        String output = "";

        ArrayList<String> tempKeys = new ArrayList<String>(tempOutputMap.keySet());
        ArrayList<Double> tempValues = new ArrayList<Double>(tempOutputMap.values());
        TreeSet<Double> sortedSet = new TreeSet<Double>(tempValues);

        Object[] sortedArray = sortedSet.toArray();
        if(sortedArray.length==0)
            return null;
        int lastIndex = sortedArray.length-1;
        Double max =(Double) sortedArray[lastIndex];
        output = (String) tempKeys.get(tempValues.indexOf((Double) sortedArray[lastIndex]));
        out.println("score: "+max);
        return output;
    }

    /**
     * @return the misClassifications
     */
    public int getMisClassifications() {
        return misClassifications;
    }

    /**
     * @param misClassifications the misClassifications to set
     */
    public void setMisClassifications(int misClassifications) {
        this.misClassifications = misClassifications;
    }

    /**
     * @return the trainData
     */
    public DataSet getTrainData() {
        return trainData;
    }

    /**
     * @param trainData the trainData to set
     */
    public void setTrainData(DataSet trainData) {
        this.trainData = trainData;
    }

    /**
     * @return the testData
     */
    public DataSet getTestData() {
        return testData;
    }

    /**
     * @param testData the testData to set
     */
    public void setTestData(DataSet testData) {
        this.testData = testData;
    }

    /**
     * @return the positiveClassifications
     */
    public int getPositiveClassifications() {
        return positiveClassifications;
    }

    /**
     * @param positiveClassifications the positiveClassifications to set
     */
    public void setPositiveClassifications(int positiveClassifications) {
        this.positiveClassifications = positiveClassifications;
    }
    public double[] calculateWeights(int howMany){
        Random randomGenerator;
        double random;
        
        double[] weights = new double[howMany];

        for(int i =0; i<howMany;i++){
            randomGenerator = new Random();
            random = randomGenerator.nextDouble();
            weights[i]=random;
        }

        double max = max(weights);
        double min = min(weights);

        double total=0;
        for(int i =0;i<howMany;i++){
            weights[i]=(weights[i]-min)/(max-min);
            total+=weights[i];
        }

        double newTotal=0;
        for(int i =0;i<howMany;i++){
            weights[i]=(1+weights[i]/total);
            newTotal+=weights[i];
        }
        this.trainData.setWeights(weights);
        return weights;
    }

    public void adjustWeight(int index, double weight){
        double[] weights = this.trainData.getWeights();
        weights[index]=weight;
        this.trainData.setWeights(weights);
    }

    public void setWeights(double weights[]){
        this.trainData.setWeights(weights);
    }

    public double[] adjustWeights(double error, double learningRate){
        double[] weights = this.trainData.getWeights();
        int howMany=weights.length;
        for(int i =0; i<howMany;i++){
            weights[i]=weights[i]+(weights[i]*learningRate*error);
        }

        double max = max(weights);
        double min = min(weights);
        

        double total = 0;
        for(int i =0;i<howMany;i++){
            weights[i]=(weights[i]-min)/(max-min);
            total+=weights[i];
        }

        
        double newTotal=0;
        for(int i =0;i<howMany;i++){
            weights[i]=(1+weights[i]/total);
            newTotal+=weights[i];
        }

        
        this.trainData.setWeights(weights);
        return weights;
    }

    public double max(double[] t) {
    double maximum = t[0];   // start with the first value
    for (int i=1; i<t.length; i++) {
        if (t[i] > maximum) {
            maximum = t[i];   // new maximum
        }
    }
    return maximum;
    }

    public double min(double[] t) {
    double minimum = t[0];   // start with the first value
    for (int i=1; i<t.length; i++) {
        if (t[i] < minimum) {
            minimum = t[i];   // new maximum
        }
    }
    return minimum;
    }
    
    public static double average(double[] t) {
    double total = 0;   // start with the first value
    int count=1;
    for (int i=0; i<t.length; i++) {
        total+=t[i];
        count++;
    }
    return total/count;
    }
}
